package apsp;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class APSP {
	
	public static void main(String[] args){
		try{
		  
		  APSP apsp=new APSP();
		  apsp.Process();
		}
		catch(Exception e){
			e.getMessage();
		}
		
	}
	
	public void AllPairShortestPath(int cost[][],int index)
	{
		try{
		PrintWriter pr = new PrintWriter(new FileWriter("output.txt"));
		int[][]dist = new int [index][index];
		
//cost is input matrix	
		for(int i=0;i<index;i++)
		{
			for(int j=0;j<index;j++)
			{
				dist[i][j]=cost[i][j];     
			}
		}
		
// All Pair shorting Algorithm 
		for(int k=0;k<index;k++)
		{
		   for(int i=0;i<index;i++)
		     {
			     for(int j=0;j<index;j++)
			        {
			    	 if(dist[i][j]>(dist[i][k]+dist[k][j]))
			    	 {
			    		 dist[i][j]=dist[i][k]+dist[k][j];
			    	 }
			        }
		     }
		}
		
		for(int i=0;i<index;i++)
		{
			for(int j=0;j<index;j++)
			{
				pr.print(dist[i][j]+" ");
				
			}
			pr.println();
		}	
		pr.println();
		pr.close();
		
		for(int i=0;i<index;i++)
		{
			for(int j=0;j<index;j++)
			{
				System.out.print(dist[i][j]+" ");
				
			}
			System.out.println();
		}
		}
		catch(Exception e){
			e.getMessage();
		}
	  }
	public void Process(){	  
		  
		  try 
		  {
			  int cost[][]= new int [100][100];
			  int dist[] = new int [100];
			  BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
			  String string = "";
			  
			  int i=0;
			  System.out.println("Input array is : ");
			  while ((string = br.readLine())!=null)
			  {
			//   System.out.println(string); // read each line of string
			   StringTokenizer sTokrn = new StringTokenizer(string);
			   int j=0;
			   while(sTokrn.hasMoreTokens()){
			    String subString = sTokrn.nextToken();
			    cost[i][j]= Integer.parseInt(subString);
			    System.out.print(" "+cost[i][j]);
			    j++;
			   }
			   i++;
			   System.out.println();
			  }
			    
			AllPairShortestPath(cost, i);
		  } 
		  catch (Exception e) 
		  {
			
			e.printStackTrace();
		  }
			
			 
		 }
				
}